介紹
在開始介紹XGBoost之前，我們先來了解一下什麼事Boosting？

所謂的Boosting 就是一種將許多弱學習器(weak learner)集合起來變成一個比較強大的學習器(strong learner)，大致上的核心思想就是「三個臭皮匠勝過一個諸葛亮」。

XGBoost ( Extreme Gradient Boosting )，是一種Gradient Boosted Tree(GBDT)，每一次保留原來的模型不變，並且加入一個新的函數至模型中，修正上一棵樹的錯誤，以提升整體的模型。主要用於解於監督是學習，可以用於分類也可以用於迴歸問題

Tree Boosting

上面提到XGBoost是一組分類和回歸樹(classification and regression trees — CART)，每一顆回歸樹的葉子都會對應到一組分數，這個分數作為之後分類的依據。上面的式子可以對應下面的圖片，所謂y^就是模型所計算出來的分數。

• Tree Ensemble

有學過機器學習的人應該可以知道，由上面的式子可以看到，L指的是loss function，式子後面加入一個懲罰項Ω，它可以避免我們的模型overfitting，幫助找到較好的模型。

優化模型最常使用的模型就是透過梯度來解決，但我們無法在一次訓練所有的樹，因此會透過增量訓練 (additive training) 的方式，每一步都是在前一步的基礎上增加一棵樹來做修正。

我們把loss function展開來看就會變成：

再將loss function以MSE表示：

再利用泰勒展開式做展開 ：

其中gi及hi定義如下：

把常數項拿掉即可得到下面式子：

• 計算每一棵樹葉子的分數

將上式重新整理後可得：

其中Gi及Hi分別為：

所以我們可以從上面的一元二次方程式得到：

所以loss function為：

上面所得到的式子可以用來判斷一棵樹的好壞

• 建構一棵樹時所進行的特徵劃分
  在這裡所使用的方式為exact greedy algorithm及approximate algorithm，就是在樹的每個層構建的過程中，來優化目標。
  1. exact greedy algorithm: 此方法會列出所有的特徵，並以此特徵當作劃分條件，透過下面的式子把每個特徵所對應的參數帶入，值越大代表損失下降越多，並找出最好的劃分點。
  2. approximate algorithm: 對於某個特徵，算法首先根據特徵分佈的分位數找到切割點的集合Sk={sk1,sk2,…,skl}；然後將特徵k的值根據集合Sk劃分到bucket中，接著對每個bucket的樣本統計值G、H進行累加統計，最後在這些累計的統計量上尋找最佳分裂點。
  3. weighted quantile sketch: 是為了解決數據無法一次載入內存或者在分佈式情況下（exact greedy algorithm）效率低的問題
  4. Sparsity-aware Split Finding : 很多時候訓練數據都是稀疏的，數據都是有缺失值的。訓練數據的時候，它使用沒有缺失的數據去進行節點分支。然後我們將特徵上缺失的數據嘗試放左右節點上，看缺失值應當分到那個分支節點上(default分支)。

• System Design:
  在建構一棵樹時最耗時間的就是尋找特徵的劃分過程中，必須先將每一個特徵先做排序。為了減少排序的時間，所以採用block來存取數據。

  1. block中的數據以稀疏格式CSC存取(目的是為了壓縮矩陣，減少矩陣存儲所佔用的空間)
  2. block中的特徵進行排序，只需要排序一次，以後分裂樹的過程可以重複使用

• Cache-aware Access:
  對於有大量數據或者說分佈式系統來說，我們不可能將所有的數據都放進內存裡面。因此我們都需要將其放在外存上或者分佈式存儲。但是這有一個問題，這樣做每次都要從外存上讀取數據到內存，這將會是十分耗時的操作。因此我們使用預讀取（prefetching）將下一塊將要讀取的數據預先放進內存裡面。其實就是多開一個線程，該線程與訓練的線程獨立並負責數據讀取。此外，還要考慮block的大小問題。如果我們設置最大的block來存儲所有樣本在k特徵上的值和梯度的話，cache未必能一次性處理如此多的梯度做統計。如果我們設置過少block size，這樣不能充分利用的多線程的優勢，也就是訓練線程已經訓練完數據，但是prefetching thread還沒把數據放入內存或者cache中。作者發現block size設置為2¹⁶個examples最好。

  
  

• Blocks for Out-of-core Computation:
  對於超大型的數據，不可能都放入放入內存，因此大部分都放入外存上。假如將數據存於外存上將帶來讀寫速度受限的問題。paper有提到兩種方法，一種是對數據進行壓縮存於外存中，到內存中需要訓練時再解壓，這樣來增加系統的吞吐率，儘管消耗了一些時間來做編碼和解碼但還是值得的。另一種就是多外存存儲，其實本質上就是分佈式存儲。

參考文獻

1. XGBoost: A Scalable Tree Boosting System
2. XGBoost-Kaggle 競賽最常被使用的演算法之一
3. XGBoost入門系列第一講
4. XGBoost論文閱讀及其原理
5. 我愛機器學習 集成學習（三）XGBoost